/*
 * @lc app=leetcode.cn id=81 lang=typescript
 *
 * [81] 搜索旋转排序数组 II
 */

// @lc code=start
function search(nums: number[], target: number): boolean {
  const n = nums.length;
  if (n === 1) return nums[0] === target;
  if (nums[0] === target) return true;

  let head = 0;
  let tail = n - 1;
  let mid: number;

  // 由于重复元素，避免mid位置的元素和头尾元素相等，无法二分
  while (head < tail && nums[head] === nums[0]) {
    head++;
  }
  while (head < tail && nums[tail] === nums[0]) {
    tail--;
  }

  while (head <= tail) {
    mid = head + ((tail - head) >> 1);
    if (nums[mid] === target) return true;
    if (nums[mid] <= nums[tail]) {
      // nums[mid]在右边升序区间中
      if (target > nums[mid] && target <= nums[tail]) {
        head = mid + 1;
      } else {
        tail = mid - 1;
      }
    } else {
      // nums[mid]在左边升序区间中
      if (target < nums[mid] && target >= nums[head]) {
        tail = mid - 1;
      } else {
        head = mid + 1;
      }
    }
  }

  return false;
}
// @lc code=end
